//https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked

//https://zhuanlan.zhihu.com/p/374041523

#include <iostream>
#include <vector>
#include <climits>
#include <stack>
#include <queue>
#include <list>
#include <map>

using namespace std;

#include <iostream>
#include <list>
#include <unordered_map>

class LRU {
public:
    int capacity;
    std::list<std::pair<int, int>> l;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> m;
public:
    LRU(int c) : capacity(c) {};
    int Get(int key);
    void Put(int key, int value);
};
// 获取数据，并将该数据放到 list 头部
int LRU::Get(int key)
{
    if (m.find(key) != m.end()) {
        std::pair<int, int> p = *(m[key]);
        l.erase(m[key]);
        l.push_front(p);
        m[key] = l.begin();
        return p.second;
    } else {
        return -1;
    }
}
// 插入数据，如果 key 已存在，则更新，否则插入。并将它放置到 list 头部
// 如果 list 中数据满了，移除其尾部数据。
void LRU::Put(int key, int value)
{
    if (m.find(key) != m.end()) {
        l.erase(m[key]);
        l.push_front({key, value});
        m[key] = l.begin();
    } else {
        if (l.size() >= capacity) {
            auto last = l.back();
            l.pop_back();
            m.erase(last.first);
            l.push_front(std::make_pair(key, value));
            m.insert({key, l.begin()});
        } else {
            l.push_front({key, value});
            m.insert({key, l.begin()});
        }
    }
}


class LFUCache {
public:
    map<int, int> freq;  // key - cnt 
    map<int, list<pair<int, int>>> lfu;  // cnt - list<key, value>
    map<int, list<pair<int, int>>::iterator> pos;  // key - iterator
    int capacity;

public:
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        int value;
        auto it = pos.find(key);
        if (it != pos.end()) {  // 计数 +1，并重排序
            value = it->second->second;
            int cnt = freq[key];
            freq[key]++;
            lfu[cnt].erase(it->second);
            if (lfu[cnt].empty()) {
                lfu.erase(cnt);  // 清空 key
            }
            auto newIter = lfu[cnt + 1].insert(lfu[cnt + 1].begin(), {key, value});
            pos[key] = newIter;
        } else {
            value = -1;
        }
        return value;
    }

    void put(int key, int value) {  // 更新已经存在的某个 key
        if (capacity == 0) {
            return;
        }
        auto it = pos.find(key);
        if (freq.size() == capacity) {
            if ((it == pos.end())) {
                // delete old one
                auto it2 = lfu.begin()->second.rbegin();
                int deleteKey = it2->first;
                int cnt = freq[deleteKey];
                freq.erase(deleteKey);
                pos.erase(deleteKey);
                lfu[cnt].pop_back();
                if (lfu[cnt].empty()) {
                    lfu.erase(cnt);
                }
                freq[key] = 1;
            } else {
                lfu[freq[key]].erase(it->second);
                if (lfu[freq[key]].empty()) {
                    lfu.erase(freq[key]);
                }
                freq[key]++;
            }
        } else {
            if (it == pos.end()) {
                freq[key] = 1;
            } else {
                lfu[freq[key]].erase(it->second);
                if (lfu[freq[key]].empty()) {
                    lfu.erase(freq[key]);
                }
                freq[key]++;
            }
        }
        // add new one
        auto newIter = lfu[freq[key]].insert(lfu[freq[key]].begin(), {key, value});
        pos[key] = newIter;
    }
};